{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1599447407068",
   "display_name": "Python 3.8.5 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 347. 前 K 个高频元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个非空的整数数组，返回其中出现频率前 k 高的元素。\n",
    "\n",
    " \n",
    "```\n",
    "示例 1:\n",
    "\n",
    "输入: nums = [1,1,1,2,2,3], k = 2\n",
    "输出: [1,2]\n",
    "示例 2:\n",
    "\n",
    "输入: nums = [1], k = 1\n",
    "输出: [1]\n",
    "``` \n",
    "\n",
    "提示：\n",
    "\n",
    "你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。\n",
    "你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。\n",
    "题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。\n",
    "你可以按任意顺序返回答案。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/top-k-frequent-elements\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return [i[0] for i in counter.most_common(k)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Help on Counter in module collections object:\n\nclass Counter(builtins.dict)\n |  Counter(iterable=None, /, **kwds)\n |  \n |  Dict subclass for counting hashable items.  Sometimes called a bag\n |  or multiset.  Elements are stored as dictionary keys and their counts\n |  are stored as dictionary values.\n |  \n |  >>> c = Counter('abcdeabcdabcaba')  # count elements from a string\n |  \n |  >>> c.most_common(3)                # three most common elements\n |  [('a', 5), ('b', 4), ('c', 3)]\n |  >>> sorted(c)                       # list all unique elements\n |  ['a', 'b', 'c', 'd', 'e']\n |  >>> ''.join(sorted(c.elements()))   # list elements with repetitions\n |  'aaaaabbbbcccdde'\n |  >>> sum(c.values())                 # total of all counts\n |  15\n |  \n |  >>> c['a']                          # count of letter 'a'\n |  5\n |  >>> for elem in 'shazam':           # update counts from an iterable\n |  ...     c[elem] += 1                # by adding 1 to each element's count\n |  >>> c['a']                          # now there are seven 'a'\n |  7\n |  >>> del c['b']                      # remove all 'b'\n |  >>> c['b']                          # now there are zero 'b'\n |  0\n |  \n |  >>> d = Counter('simsalabim')       # make another counter\n |  >>> c.update(d)                     # add in the second counter\n |  >>> c['a']                          # now there are nine 'a'\n |  9\n |  \n |  >>> c.clear()                       # empty the counter\n |  >>> c\n |  Counter()\n |  \n |  Note:  If a count is set to zero or reduced to zero, it will remain\n |  in the counter until the entry is deleted or the counter is cleared:\n |  \n |  >>> c = Counter('aaabbc')\n |  >>> c['b'] -= 2                     # reduce the count of 'b' by two\n |  >>> c.most_common()                 # 'b' is still in, but its count is zero\n |  [('a', 3), ('c', 1), ('b', 0)]\n |  \n |  Method resolution order:\n |      Counter\n |      builtins.dict\n |      builtins.object\n |  \n |  Methods defined here:\n |  \n |  __add__(self, other)\n |      Add counts from two counters.\n |      \n |      >>> Counter('abbb') + Counter('bcc')\n |      Counter({'b': 4, 'c': 2, 'a': 1})\n |  \n |  __and__(self, other)\n |      Intersection is the minimum of corresponding counts.\n |      \n |      >>> Counter('abbb') & Counter('bcc')\n |      Counter({'b': 1})\n |  \n |  __delitem__(self, elem)\n |      Like dict.__delitem__() but does not raise KeyError for missing values.\n |  \n |  __iadd__(self, other)\n |      Inplace add from another counter, keeping only positive counts.\n |      \n |      >>> c = Counter('abbb')\n |      >>> c += Counter('bcc')\n |      >>> c\n |      Counter({'b': 4, 'c': 2, 'a': 1})\n |  \n |  __iand__(self, other)\n |      Inplace intersection is the minimum of corresponding counts.\n |      \n |      >>> c = Counter('abbb')\n |      >>> c &= Counter('bcc')\n |      >>> c\n |      Counter({'b': 1})\n |  \n |  __init__(self, iterable=None, /, **kwds)\n |      Create a new, empty Counter object.  And if given, count elements\n |      from an input iterable.  Or, initialize the count from another mapping\n |      of elements to their counts.\n |      \n |      >>> c = Counter()                           # a new, empty counter\n |      >>> c = Counter('gallahad')                 # a new counter from an iterable\n |      >>> c = Counter({'a': 4, 'b': 2})           # a new counter from a mapping\n |      >>> c = Counter(a=4, b=2)                   # a new counter from keyword args\n |  \n |  __ior__(self, other)\n |      Inplace union is the maximum of value from either counter.\n |      \n |      >>> c = Counter('abbb')\n |      >>> c |= Counter('bcc')\n |      >>> c\n |      Counter({'b': 3, 'c': 2, 'a': 1})\n |  \n |  __isub__(self, other)\n |      Inplace subtract counter, but keep only results with positive counts.\n |      \n |      >>> c = Counter('abbbc')\n |      >>> c -= Counter('bccd')\n |      >>> c\n |      Counter({'b': 2, 'a': 1})\n |  \n |  __missing__(self, key)\n |      The count of elements not in the Counter is zero.\n |  \n |  __neg__(self)\n |      Subtracts from an empty counter.  Strips positive and zero counts,\n |      and flips the sign on negative counts.\n |  \n |  __or__(self, other)\n |      Union is the maximum of value in either of the input counters.\n |      \n |      >>> Counter('abbb') | Counter('bcc')\n |      Counter({'b': 3, 'c': 2, 'a': 1})\n |  \n |  __pos__(self)\n |      Adds an empty counter, effectively stripping negative and zero counts\n |  \n |  __reduce__(self)\n |      Helper for pickle.\n |  \n |  __repr__(self)\n |      Return repr(self).\n |  \n |  __sub__(self, other)\n |      Subtract count, but keep only results with positive counts.\n |      \n |      >>> Counter('abbbc') - Counter('bccd')\n |      Counter({'b': 2, 'a': 1})\n |  \n |  copy(self)\n |      Return a shallow copy.\n |  \n |  elements(self)\n |      Iterator over elements repeating each as many times as its count.\n |      \n |      >>> c = Counter('ABCABC')\n |      >>> sorted(c.elements())\n |      ['A', 'A', 'B', 'B', 'C', 'C']\n |      \n |      # Knuth's example for prime factors of 1836:  2**2 * 3**3 * 17**1\n |      >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})\n |      >>> product = 1\n |      >>> for factor in prime_factors.elements():     # loop over factors\n |      ...     product *= factor                       # and multiply them\n |      >>> product\n |      1836\n |      \n |      Note, if an element's count has been set to zero or is a negative\n |      number, elements() will ignore it.\n |  \n |  most_common(self, n=None)\n |      List the n most common elements and their counts from the most\n |      common to the least.  If n is None, then list all element counts.\n |      \n |      >>> Counter('abracadabra').most_common(3)\n |      [('a', 5), ('b', 2), ('r', 2)]\n |  \n |  subtract(self, iterable=None, /, **kwds)\n |      Like dict.update() but subtracts counts instead of replacing them.\n |      Counts can be reduced below zero.  Both the inputs and outputs are\n |      allowed to contain zero and negative counts.\n |      \n |      Source can be an iterable, a dictionary, or another Counter instance.\n |      \n |      >>> c = Counter('which')\n |      >>> c.subtract('witch')             # subtract elements from another iterable\n |      >>> c.subtract(Counter('watch'))    # subtract elements from another counter\n |      >>> c['h']                          # 2 in which, minus 1 in witch, minus 1 in watch\n |      0\n |      >>> c['w']                          # 1 in which, minus 1 in witch, minus 1 in watch\n |      -1\n |  \n |  update(self, iterable=None, /, **kwds)\n |      Like dict.update() but add counts instead of replacing them.\n |      \n |      Source can be an iterable, a dictionary, or another Counter instance.\n |      \n |      >>> c = Counter('which')\n |      >>> c.update('witch')           # add elements from another iterable\n |      >>> d = Counter('watch')\n |      >>> c.update(d)                 # add elements from another counter\n |      >>> c['h']                      # four 'h' in which, witch, and watch\n |      4\n |  \n |  ----------------------------------------------------------------------\n |  Class methods defined here:\n |  \n |  fromkeys(iterable, v=None) from builtins.type\n |      Create a new dictionary with keys from iterable and values set to value.\n |  \n |  ----------------------------------------------------------------------\n |  Data descriptors defined here:\n |  \n |  __dict__\n |      dictionary for instance variables (if defined)\n |  \n |  __weakref__\n |      list of weak references to the object (if defined)\n |  \n |  ----------------------------------------------------------------------\n |  Methods inherited from builtins.dict:\n |  \n |  __contains__(self, key, /)\n |      True if the dictionary has the specified key, else False.\n |  \n |  __eq__(self, value, /)\n |      Return self==value.\n |  \n |  __ge__(self, value, /)\n |      Return self>=value.\n |  \n |  __getattribute__(self, name, /)\n |      Return getattr(self, name).\n |  \n |  __getitem__(...)\n |      x.__getitem__(y) <==> x[y]\n |  \n |  __gt__(self, value, /)\n |      Return self>value.\n |  \n |  __iter__(self, /)\n |      Implement iter(self).\n |  \n |  __le__(self, value, /)\n |      Return self<=value.\n |  \n |  __len__(self, /)\n |      Return len(self).\n |  \n |  __lt__(self, value, /)\n |      Return self<value.\n |  \n |  __ne__(self, value, /)\n |      Return self!=value.\n |  \n |  __reversed__(self, /)\n |      Return a reverse iterator over the dict keys.\n |  \n |  __setitem__(self, key, value, /)\n |      Set self[key] to value.\n |  \n |  __sizeof__(...)\n |      D.__sizeof__() -> size of D in memory, in bytes\n |  \n |  clear(...)\n |      D.clear() -> None.  Remove all items from D.\n |  \n |  get(self, key, default=None, /)\n |      Return the value for key if key is in the dictionary, else default.\n |  \n |  items(...)\n |      D.items() -> a set-like object providing a view on D's items\n |  \n |  keys(...)\n |      D.keys() -> a set-like object providing a view on D's keys\n |  \n |  pop(...)\n |      D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n |      If key is not found, d is returned if given, otherwise KeyError is raised\n |  \n |  popitem(self, /)\n |      Remove and return a (key, value) pair as a 2-tuple.\n |      \n |      Pairs are returned in LIFO (last-in, first-out) order.\n |      Raises KeyError if the dict is empty.\n |  \n |  setdefault(self, key, default=None, /)\n |      Insert key with a value of default if key is not in the dictionary.\n |      \n |      Return the value for key if key is in the dictionary, else default.\n |  \n |  values(...)\n |      D.values() -> an object providing a view on D's values\n |  \n |  ----------------------------------------------------------------------\n |  Static methods inherited from builtins.dict:\n |  \n |  __new__(*args, **kwargs) from builtins.type\n |      Create and return a new object.  See help(type) for accurate signature.\n |  \n |  ----------------------------------------------------------------------\n |  Data and other attributes inherited from builtins.dict:\n |  \n |  __hash__ = None\n\nNone\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[1, 2]"
     },
     "metadata": {},
     "execution_count": 10
    }
   ],
   "source": [
    "Solution().topKFrequent([1,1,1,2,2,3],2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}